package pers.sloera.leetcode.editor.cn;

import cn.hutool.core.lang.Assert;

import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 交换字符使得字符串相同
 *
 * @author sloera
 * @date 2023-02-25 21:59:24
 */
class MinimumSwapsToMakeStringsEqual {
    public static void main(String[] args) {
        Solution solution = new MinimumSwapsToMakeStringsEqual().new Solution();
        Assert.isTrue(solution.minimumSwap("xxyyxyxyxx", "xyyxyxxxyx") == 4);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minimumSwap(String s1, String s2) {
            List<Integer> leftList = s1.chars().boxed().collect(Collectors.toList());
            List<Integer> rightList = s2.chars().boxed().collect(Collectors.toList());
            removeSameChar(rightList, leftList);
            // 不相同的为单数，除了xx,xy,yy，必然剩一个无法平衡
            if (leftList.size() % 2 != 0) {
                return -1;
            }
            Map<Integer, Long> leftMap = leftList.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
            Map<Integer, Long> rightMap = rightList.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
            Integer xChar = (int) 'x';
            Integer yChar = (int) 'y';
            // 相同位置相同字符的已经被移除，剩余都需要移动位置，可匹配的xx/yy和xy/yx，如果x和y总数不相等，肯定不能平衡
            if (leftMap.getOrDefault(xChar, 0L) + rightMap.getOrDefault(xChar, 0L) != leftMap.getOrDefault(yChar, 0L) + rightMap.getOrDefault(yChar, 0L)) {
                return -1;
            }
            int ret = 0;
            // 经示例可得， xx/yy 只需要一次，xy/yx需要两次
            ret += leftMap.getOrDefault(xChar, 0L) >> 1; // 添加xx
            ret += leftMap.getOrDefault(yChar, 0L) >> 1; // 添加yy
            // xy 需要两次。 最多只有一个xy
            if (leftMap.getOrDefault(xChar, 0L) % 2 != 0 || leftMap.getOrDefault(yChar, 0L) % 2 != 0) {
                ret += 2;
            }
            return ret;
        }

        // 去除相同位置相同的字符
        private void removeSameChar(List<Integer> rightList, List<Integer> leftList) {
            Iterator<Integer> leftIt = leftList.iterator();
            int i = 0;
            while (leftIt.hasNext()) {
                Integer next = leftIt.next();
                if (rightList.get(i).equals(next)) {
                    rightList.remove(i);
                    leftIt.remove();
                    i--;
                }
                i++;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
